In a multiprocessor system having a shared memory and bus, a private cache is conventionally provided to each processor to decrease conflicts of access to a bus and memory. In the present invention a mechanism is accordingly required for guaranteeing data consistency or coherency among a plurality of caches. One of such mechanisms is known as a Snoop Cache technique.
FIG. 1 shows a prior art multiprocessor system of the snoop cache type, wherein a plurality of processors 1a through 1n are connected to a shared bus 4 and a shared memory 5 via private caches 2a through 2n respectively. Controllers 3a through 3n are provided to the private caches 2a through 2n respectively to monitor signals on the shared bus 4 and to achieve data coherency in this distributed configuration. In other words, in a system of this type, the controllers 3a through 3n operate following a protocol for the shared bus 4a to attain data coherency.
Conventional protocols of prior art are divided into the invalidate type and the update type in regard to the way in which, when any of the processors 1a through 1n, writes data in a corresponding private, cache 2a through 2n, data having the same address termed corresponding or shared data, in the remaining caches 2a through 2n is manipulated. In the invalidate type protocol, data having the same address in the remaining caches 2a through 2n are all invalidated to maintain data coherency. On the other hand, in the update type protocol, all the copies in the same address are updated to the same value as the written data by any of processors 1a through 1n, and data coherency is maintained.
More specifically, an operation for guaranteeing data coherency upon a write operation for each modification type is performed as follows. Each line of each private cache is provided with one bit of information referred to as a tag, which indicates the line has data "exclusively" or "shares" it with one or more other caches. Only if data of a line of a private cache is "shared" when a related processor writes in the line of the private cache, a related controller takes the shared bus to perform a procedure for guaranteeing data coherency, and submits request signals to all the other caches to perform required operations.
FIG. 2 shows an operation in the prior art invalidate type, wherein as shown, a certain shared data in the cache 2a is subjected to a write operation, the cache 2b has the shared data, and the cache 2c does not. The requesting controller 3a of the cache 2a transmits a request signal onto the shared bus 4, and changes the tag of own shared data to "exclusive". The controller 3b of the cache 2b which has the shared data recognizes the request signal on the shared bus 4, and invalidates the shared data because it has the data of the same address. In the other cache 2c no operation is performed because it does not have the shared data.
FIG. 3 shows an operation in the prior art of the update type. In this case, the caches 2a and 2b have shared data, where the shared data in the cache 2a is subjected to a write operation. In this figure, the requesting controller 3a of the cache 2a, after submitting a request signal and update data on the shared bus, waits for a reply signal, and determines its own tag based on that reply signal. The controller 3b of the cache 2b having the shared data recognizes the request signal and updates data on the shared bus 4, and since it has data having the same address it updates the data with the update data and responds with a positive reply signal. The reply signal is next wired ORed with other like replies and then returned to the requesting controller 3a of the cache 2a. The resulting reply is used to set the data word tag.
Here the positive value represents that "the data is shared by at least one other cache", and the negative value means that "the data is never shared by any other cache". Accordingly when a positive reply signal is returned, then the requesting cache becomes "shared", otherwise it becomes "exclusive".
In general, the update type is superior to the invalidate type because the former provides a higher data hit rate. In the update type, however, bus contention occurs more frequently since it is more probable that accessed data is shared so bus access occurs more frequently during a data write operation. Consequently, which modification protocol type is more suitable cannot be determined in general; it depends on characteristics of the program to be run and operational circumstances of a particular processor. It is, accordingly, required to switch among protocol types based on different circumstances.
In order to achieve a system able to switch protocols, it may be proposed that a controller perform both the invalidate type and update type protocols, and further means is provided to switch the modification type based on the situations. In this proposal there are two problems. First, since conventional protocol types are designed for a complete system, if a modification type for each cache is switched, protocols are different from one cache to another and data coherency cannot be achieved. For example, when shared data of a first cache is subjected to a write operation, and the first cache is of the invalidate type, and a second cache having the same shared data is of the update type, then the second cache has the shared data updated while the first cache subjected to the write operation has the data tagged as exclusive (in the invalidate type any shared data subjected to a write operation is changed to exclusive). Accordingly, when the data in the first cache of the invalidate type is later subjected to a write operation, the write operation does not reflect the data in the second cache, and then data coherency between the two caches is lost. Second, if all the modification types over the system are switched simultaneously, data coherency can be maintained. However, for this purpose, when all the caches are switched simultaneously, synchronization is required over the system, prohibiting any memory access during the synchronization. Accordingly, dynamic switching cannot be practically performed at run time.
In addition, the following prior art is identified as relevant to the present invention: Preparation of More Than One Cache Memory for a System and Switch and Use of Those Caches (Japanese Published Unexamined Patent Application, JPUPA No. 51-139736, and JPUPA No. 52-80747); Switching Block Replacement Modes for a Cache Memory (JPUPA No. 51-32241, JPUPA No. 50-65141 and JPUPA No. 50-73530); and Switching Storage Modes of a Cache Memory (JPUPA No. 53-65025). However, this prior art does not suggest switching protocols for individual private caches.
In consideration of the above, it is an object of the present invention to provide a multiprocessor system wherein a modification type can be changed for each cache individually, and a modification type can be dynamically changed for each cache at run time.